package org.leetcode.middle.leetcode518;

import java.util.Arrays;

public class Solution {

    public int change3(int amount, int[] coins) {
        backtracking(amount,coins,0,0);
        return count;
    }

    int count = 0;

    private void backtracking(int amount, int[] coins, int currAmount, int index) {
        if (currAmount == amount) {
            count++;
            return;
        }

        if (index == coins.length || currAmount > amount) {
            return;
        }

        currAmount=currAmount+coins[index];
        backtracking(amount, coins, currAmount, index);
        currAmount=currAmount-coins[index];

        backtracking(amount, coins, currAmount, index + 1);
    }

    public int change2(int amount, int[] coins) {

        int[] dp = new int[amount + 1];

        int n = coins.length;

        dp[0] = 1;

        for (int i = 0; i < n; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                //dp[j]表示不选择当前的coin有多少种组成
                //dp[j-coins[i]]表示选择当前的coin有多少种组成
                dp[j] = dp[j] + dp[j - coins[i]];
            }
        }

        for (int i = 0; i <=amount; i++) {
            for (int j = 0; j <coins.length; j++) {
                if (j>=coins[i]){
                    dp[j] = dp[j] + dp[j - coins[i]];
                }
            }
        }

        return dp[amount];
    }

    public int change(int amount, int[] coins) {

        int[] dp = new int[amount + 1];

        dp[0] = 1;

        //组合
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] = dp[j] + dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
}
